/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
int search(int* nums, int left, int numsSize, int target) {
    int begin = left;
    int end = numsSize - 1;

    while (begin <= end)
    {
        int mid = (begin + end) / 2;

        if (nums[mid] < target)
        {
            begin = mid + 1;
        }
        else if (nums[mid] > target)
        {
            end = mid - 1;
        }
        else if (nums[mid] == target)
        {
            return mid;
        }
    }
    return -1;
}

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int* index = (int*)malloc(sizeof(int) * 2);
    if (NULL == index)
    {
        perror("malloc fail");
        exit(-1);
    }
    *returnSize = 2;

    for (int i = 0; i < numbersSize; ++i)
    {
        int sub = target - numbers[i];
        int flag = search(numbers, i + 1, numbersSize, sub);
        if (flag != -1)
        {
            index[0] = i + 1;
            index[1] = flag + 1;
            return index;
        }
    }

    index[0] = -1;
    index[1] = -1;
    return index;
}